home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 351-375 / disk_352 / treewalk / timings < prev    next >
Text File  |  1992-05-06  |  8KB  |  199 lines
  1. All timings run on an A1000 w/ 68010, 4Meg of fast ram & 1/2Meg of
  2. chip ram, off of a Supra 60 drive. My standard work environment was in
  3. place: interlaced morerow'ed WB screen and 50K stack, with the
  4. following active processes:
  5.  
  6. Task Pri  Address Command                          Directory
  7.   1    0   251948 jobs                             src:treewalk
  8.   2    0   250878 emacs                            src:treewalk
  9.   3    0   213e40 SupraMount
  10.   4   20   24fb38 bin:startprogs/machII            RAM DISK:
  11.   6    0   2552f0 bin:startprogs/wicon             RAM DISK:
  12.  
  13. In addition, snipit, ARexx 1.10, srt, FF, conman, installbeep the wb
  14. and mymenu were in place.
  15.  
  16. The current directory was src:treewalk, the directory tree scanned was
  17. rooted at src:tmp, consisting of about 20Meg of random stuff. It
  18. wasn't changed throughout.
  19.  
  20. Find is a PA find, available on fish disk 197.  Treewalk is the binary
  21. included in this distribution.  files is Lattice's files command,
  22. version 1.01, from Lattice C 5.02. 
  23.  
  24. Though files & treewalk are residentable, find is not. Therefore, all
  25. three commands were run non-resident to even the field. The object was
  26. to measure the algorithms used, not the implementation details.
  27.  
  28.  
  29. First test: walking a large tree.
  30.  
  31. Timings labeled "no output" were made from Rexx, via a script that
  32. ran each command 10 times, following each run by the time elapsed
  33. during the run, measured in seconds. The output was run through "grep
  34. -v src:" to throw away all output but timings and error messages. 
  35.  
  36. Timings labeled "output" consisted of one run, with the output going
  37. to standard out.
  38.  
  39.  
  40. find src:tmp -print, output: 115.62, no output:
  41. 28.04 28.00 28.14 28.08 28.10 28.02 28.02 28.08 28.00 28.18
  42. average: 28.066
  43.  
  44. treewalk dir src:tmp, output: 122.48, no output:
  45. 46.66 46.54 46.78 46.60 46.48 46.54 46.74 46.72 46.68 46.46
  46. average: 46.620
  47.  
  48. files src:tmp, output: 240.70, no output
  49. 163.58 163.64 163.50 163.30 163.54 163.96 164.10 163.44 163.00 163.36
  50. average: 163.542
  51.  
  52. note: files complained about multiple directories having to many files
  53. or being empty. It doesn't state which.
  54.  
  55.  
  56. Second test: listing files from a large file system that need to be
  57. backed up.
  58.  
  59. This was lifted from my backup script, which normally process the
  60. output. To make this more realistic, the output run through "grep -v
  61. src:" which matches the actual use during backup (being run into
  62. execio for processing by the Rexx backup script).  Once again 10
  63. iterations were run. Note: only two files actually met the entire
  64. selection criteria, which isn't unusual.
  65.  
  66.  
  67. find src:tmp -type f -newer src:last-backup ! -name *~ ! -name *.o -print
  68. 24.88 25.06 25.06 25.08 25.12 25.10 25.16 25.10 25.22 25.20
  69. average: 25.098
  70.  
  71. treewalk dir src:tmp filter "file && src:last-backup.date < date
  72.     && !(filename *= '*~' || filename *= '*.o')"
  73. 25.24 25.42 25.32 25.48 25.48 25.52 25.34 25.24 25.42 25.38
  74. average: 25.384
  75.  
  76. Files is unable to perform this search, as it lacks the ability to
  77. test for files not matching a name.
  78.  
  79.  
  80. Third test: cleaning up a large working directory.
  81.  
  82. A copy of the tree was created, and the copy is deleted in two passes:
  83. first, all files matching "*.o" were deleted, and then everything else
  84. was deleted. The deletion utility is "rm", which is a version of
  85. delete without the limit on the number of arguments. This allows
  86. treewalk to not have to invoke the command multiple times. While this
  87. may seem unfair to find, part of the purpose of creating treewalk was
  88. to overcome this disability in find. To make the test realistic, rm
  89. was resident for all runs of the test. Files has an option to cause
  90. file deletion which was used so that files would run in reasonable
  91. time.  The sources to "rm" are available upon request.
  92.  
  93. To avoid having to copy the tree multiple times, this test was run
  94. only one time for each command. Since the multiple run tests show
  95. little variance, it isn't expected that these will show much variance
  96. either.
  97.  
  98.                             time
  99. find tmp:mg -name *.o -exec rm "{}" ";"            53.76
  100. find tmp:mg -exec rm "{}" ";"                150.68
  101.  
  102. Note: Find doesn't support AmigaDOS wildcarding.
  103. Note: Find failed to delete any directories during the second phase of
  104. the trial, even though it deleted all regular files.
  105.  
  106. treewalk dir tmp:mg filter "filename#='#?.o'" rm    24.40
  107. treewalk post dir tmp:mg rm                50.66
  108.  
  109. Note: to insure that directories are seen after files, treewalk needs
  110. to be told to do a postorder traversal of the tree during the second
  111. phase.
  112. Note: treewalk did not delete the top-level directory, but this is to
  113. be expected from it's documentation.
  114.  
  115. files -rerase -name #?.o tmp:mg                353.14
  116. files -rerase tmp:mg                    159.88
  117.  
  118. Note: files complains that it can't delete certain directories during
  119. the first phase. This is odd and somewhat annoying.
  120.  
  121. As a couple of asides, I ran the filtered treewalk file removal,
  122. forcing treewalk to run a single copy of rm for each file to delete
  123. (the same behavior that find uses) to gain some measure of how
  124. important the ability to stack file names on a command is. I then ran
  125. the full delete using the standard AmigaDOS delete command, to see how
  126. that compared with the other cases.
  127.  
  128. treewalk dir tmp:mg filter "filename#='#?.o'" single rm    43.38
  129. delete tmp:mg all quiet                    32.64
  130.  
  131.  
  132. Final note: program sizes.
  133.  
  134. find                       13044 ----rwed 19-Apr-89 02:29:43
  135. treewalk                   19904 --p-rwed Today     21:37:31
  136. files                      24096 --p-rwed 19-Apr-89 02:30:22
  137.  
  138.  
  139. Some statistics:
  140.  
  141. Running time as a percentage of the slowest program. Times for
  142. multiple run tests are the average.
  143.  
  144.     program        files        find        treewalk    <aside>
  145. test
  146. 1 output        100        48         51
  147. 1 no output        100        17         29
  148. 2            not possible    99        100
  149. 3 filtered        100        15          7         12
  150. 3 unfiltered        100        94         32        20
  151. total 1 & 3        100        38         26
  152.  
  153.  
  154. Conclusions:
  155.  
  156. It should be clear that files is the least worthwhile tool of the lot.
  157. It's far slower than either of the other two, not as flexible, and
  158. much larger. It's inability to distinguish between an empty directory
  159. and to many files in a directory is a serious handicap for unattended
  160. use on large devices. That source is available to the other two tools,
  161. but not to files, doesn't help. Finally, it's insistence on blaming
  162. Lattice for it's existence every time it starts just adds insult to
  163. injury.
  164.  
  165. Find appears appears to do the actual directory scanning faster than
  166. treewalk, but does most everything else slower. Possibly moving to a
  167. newer compiler technology would change this lack of speed.  However,
  168. it's inability to execute a command with multiple file arguments seems
  169. to be a major performance hit, and that appears to be inherent in it's
  170. user interface, and not solvable without a major redesign (i.e. -
  171. treewalk). It is less flexible than treewalk, not having the ability
  172. to do things like select all files that were last modified on a
  173. particular date. However, it is smaller, which could be a benefit in
  174. disk-tight situations.
  175.  
  176. Treewalk does ok for speed, but not wonderfully. In particular, if
  177. there is no filtering and the output is going to memory instead of the
  178. console, it runs slightly faster than 1/2 the speed of find. This is
  179. probably incurred by 1) not using the stack to store the visitation
  180. history, so as to avoid not using a vital resource, and 2) using a
  181. general treewalking routine instead of one that's inseparable from the
  182. program. However, it's ability to select which files to process is
  183. better than either alternative. In particular, rather than choosing a
  184. small set of primitives about files and hardwiring them into the
  185. program, it allows the user to access the data in the files
  186. FileInfoBlock, and manipulate it via C-like expressions. The addition
  187. of the ability to use ARexx macros as primitives is of unknown utility,
  188. but does allow treewalk to mimic the multiple-exec and the '-ok'
  189. features of find.
  190.  
  191. The bottom line is that there is no technical reason to use files.
  192. Find may be preferable in some cases, but treewalk is probably to be
  193. preferred in the general case.
  194.  
  195.  
  196.     Copyright 1989, Mike W. Meyer
  197.     These files may be used and redistributed under the terms
  198.     found in the file LICENSE.
  199.